import java.util.List;

/*
 * @author zzr
 * @date: 2025/03/17  19:18
 * @description: 关于链表的笔试题
 */


public class Test {

    class ListNode {
        int val;
        ListNode next;

        ListNode head;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    /**
     * 删除链表中等于给定值 val 的所有节点。
     *
     * @param head
     * @param val
     * @return
     */
    public ListNode removeElements(ListNode head, int val) {

        if (null == head) {
            return null;
        }

        ListNode cur = head.next;
        ListNode prev = head;

        while (cur != null) {
            if (val == cur.val) {
                prev.next = cur.next;
                cur = cur.next;
            } else {
                prev = cur;
                cur = cur.next;
            }
        }

        if (val == head.val) {
            head = head.next;
        }
        return head;
    }

    /**
     * 反转链表
     *
     * @param head
     * @return
     */
    public ListNode reverseList(ListNode head) {
        if (head == null) {
            return null;
        }
        if (head.next == null) {
            return head;
        }

        ListNode cur = head.next;

        head.next = null;
        while (cur != null) {
            ListNode curNext = cur.next;

            cur.next = head;
            head = cur;
            cur = curNext;

        }
        return head;
    }

    /**
     * fast每次向后走2步，slow向后走1步，当fast走到链表的最后的时候，slow的位置就是中间位置
     * 链表有奇数个节点，fast最终是fast.next == null，slow位置到达中间节点位置，偶数个节点时候，fast最终是fast == null，slow位置到达中间节点位置。
     */

    /**
     * 寻找中间节点
     *
     * @param head
     * @return
     */
    public ListNode middleNode(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;

        if (null == head) {
            return null;
        }

        if (null == head.next) {
            return head;
        }

        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    /*
    输入一个链表，输出该链表中倒数第k个结点。
     */
    public ListNode findKthToTail(ListNode head, int k) {
        if (k <= 0 || head == null) {
            return null;
        }

        ListNode fast = head;
        ListNode slow = head;

        while ((k - 1) != 0) {
            fast = fast.next;
            if (null == fast) {
                return null;
            }
            k--;
        }

        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

    /*
    将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的
     */
    public ListNode mergeTwoLists(ListNode headA, ListNode headB) {

        ListNode newHead = new ListNode();
        ListNode tmpHead = newHead;

        while (headA != null && headB != null) {
            if (headA.val > headB.val) {
                tmpHead.next = headB;
                headB = headB.next;
            } else {
                tmpHead.next = headA;
                headA = headA.next;
            }
            tmpHead = tmpHead.next;
        }

        if (headA != null) {
            tmpHead.next = headA;
        }
        if (headB != null) {
            tmpHead.next = headB;
        }

        return newHead.next;
    }

    /*
    编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前。
     */
    public ListNode partition(ListNode pHead, int x) {

        if (pHead == null) {
            return null;
        }
        ListNode as = null;
        ListNode ae = null;

        ListNode bs = null;
        ListNode be = null;

        ListNode cur = pHead;
        while (cur != null) {
            if (cur.val < x) {
                if (as == null) {
                    as = ae = cur;
                } else {
                    ae.next = cur;
                    ae = ae.next;
                }
            } else {
                if (bs == null) {
                    bs = be = cur;
                } else {
                    be.next = cur;
                    be = be.next;
                }
            }
            cur = cur.next;
        }
        //如果基准值x比较小 -- > 即基准值x左侧没有节点
        //直接返回大于等于x的节点所组成的链表头结点
        if (as == null) {
            return bs;
        }
        ae.next = bs;

        //如果val最大的节点不是最后一个节点 则手动将next置为null
        if (bs != null) {
            be.next = null;
        }
        return as;
    }

    /*
    判断 ——> 链表的回文结构
     */
    public boolean chkPalindrome(ListNode head) {

        ListNode fast = head;
        ListNode slow = head;

        //找到中间节点
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        //当上面while循环结束的时候 slow指向的就算中间节点的位置

        //反转后半部分
        ListNode cur = slow.next;
        slow.next = null;
        while (cur != null) {
            ListNode curNext = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }

        //从前 从后开始比较
        while (head != slow) {
            if (head.val != slow.val) {
                return false;
            }
            if (head.next == slow) {
                return true;
            }
            head = head.next;
            slow = slow.next;
        }
        return true;
    }

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {

        int lenA = 0;
        int lenB = 0;

        ListNode pL = headA; //设pL为长的链表
        ListNode pS = headB; //设pS为短的链表

        while (pL != null) {
            lenA++;
            pL = pL.next;
        }

        while (pS != null) {
            lenB++;
            pS = pS.next;
        }

        pL = headA;
        pS = headB;

        int len = lenA - lenB;
        if (len < 0) {
            len = lenB - lenA;
            pL = headB;
            pS = headA;
        }

        while (len != 0) {
            pL = pL.next;
            len--;
        }

        while (pS != pL) {
            pS = pS.next;
            pL = pL.next;
        }

        return pS;
    }

    /**
     * 判断链表是否有环
     *
     * @param head
     * @return
     */
    public boolean hasCycle(ListNode head) {

        if (head == null || head.next == null) {
            return false;
        }

        ListNode fast = head;
        ListNode slow = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (fast == slow) {
                return true;
            }
        }
        return false;
    }

    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }

        ListNode fast = head;
        ListNode slow = head;

        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;

            if (slow == fast) {
                break;
            }
        }

        if (fast == null || fast.next == null) {
            return null;
        }

        fast = head;
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }

        return fast;
    }

    /**
     * 删除链表中的重复节点
     * @param pHead
     * @return
     */
    public ListNode deleteDuplication(ListNode pHead) {
        ListNode cur = pHead;
        ListNode newHead = new ListNode();
        ListNode tmpHead = newHead;

        while(cur != null) {
            if(cur.next != null && cur.val == cur.next.val) {
                while(cur.next != null && cur.val == cur.next.val) {
                    cur = cur.next;
                }
                cur = cur.next;
            } else {
                tmpHead.next = cur;
                tmpHead = tmpHead.next;
                cur = cur.next;
            }
        }
        tmpHead.next = null;
        return newHead.next;
    }
}